package codingforgreat.lchot150;

public class Lc044 {
    public class Node{
        boolean res;
        public Node(boolean b){
            res = b;
        }
    }
    public boolean isMatch(String s, String p) {
        char[] str1 = s.toCharArray();
        char[] str2 = p.toCharArray();
        Node[][] map = new Node[str1.length + 1][str2.length + 1];
        return process(str1,str2,0,0,map);
    }
    public boolean process(char[] str1,char[] str2,int i,int j,Node[][] map){
        if(map[i][j] != null){
            return map[i][j].res;
        }
        boolean res = false;
        if(i == str1.length && j == str2.length){
            map[i][j] = new Node(true);
            return true;
        }else if(i == str1.length){
            res =  str2[j] == '*' && process(str1,str2,i,j + 1,map);
        }else if(j == str2.length){
            map[i][j] = new Node(false);
            return false;
        }else{
            if(str2[j] != '*' ){//a~z || ?
                res = (str1[i] == str2[j] || str2[j] == '?') && process(str1,str2,i + 1,j + 1,map);
            }else{//*
                res = process(str1,str2,i + 1,j,map) || process(str1,str2,i,j + 1,map);
            }
        }
        map[i][j] = new Node(res);
        return res;
    }
}
